Paper 2016/504

Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography

Patrick Longa and Michael Naehrig

Abstract

The Number Theoretic Transform (NTT) provides efficient algorithms for cyclic and nega-cyclic convolutions, which have many applications in computer arithmetic, e.g., for multiplying large integers and large degree polynomials. It is commonly used in cryptographic schemes that are based on the hardness of the Ring Learning With Errors (R-LWE) problem to efficiently implement modular polynomial multiplication. We present a new modular reduction technique that is tailored for the special moduli required by the NTT. Based on this reduction, we speed up the NTT and propose faster, multi-purpose algorithms. We present two implementations of these algorithms: a portable C implementation and a high-speed implementation using assembly with AVX2 instructions. To demonstrate the improved efficiency in an application example, we benchmarked the algorithms in the context of the R-LWE key exchange protocol that has recently been proposed by Alkim, Ducas, Pöppelmann and Schwabe. In this case, our C and assembly implementations compute the full key exchange 1.49 and 1.13 times faster, respectively. These results are achieved with full protection against timing attacks.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. CANS 2016
Keywords
Post-quantum cryptographynumber theoretic transform (NTT)ring learning with errors (R-LWE)fast modular reductionefficient implementation.
Contact author(s)
plonga @ microsoft com
History
2016-11-10: last of 2 revisions
2016-05-23: received
See all versions
Short URL
https://ia.cr/2016/504
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/504,
      author = {Patrick Longa and Michael Naehrig},
      title = {Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/504},
      year = {2016},
      url = {https://eprint.iacr.org/2016/504}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.